package QuestionDaily;

import java.util.*;

public class uniqueLetterString_828 {
    /**
     * 统计字符串 s 中的所有字串含有的唯一字符
     * @param s 只包含大写英文字符
     * @return 唯一字符的个数。
     */
    public int uniqueLetterString(String s) {
        /**
         * 想法是递归遍历所有字符，在每一层循环处理之前所有的子串
         * 想法失败。没办法区分子串什么时候参与运算·
         */
        char[]chars=s.toCharArray();
        function(chars,0,0);
        return sum;
    }
    List<int[]> list1=new ArrayList<>();//子串中各字符的个数
    int sum=0;

    /**
     *递归计算
     * @param index 当前字符的下标
     * @param position 当前是那个位置开始的子串
     */
    void function(char[]chars,int index,int position){
        for (int i = index; i < chars.length; i++) {
            for (int t=position;t<list1.size();t++) {        //处理之前所有的子串
                int count = list1.get(t)[chars[i] - 'A'];
                if (count == 0) { //如果该子串不包含该元素，唯一字符+1
                    list1.get(t)[chars[i] - 'A']++;
                    sum++;
                } else if (count == 1) { //如果该子串包含一个该元素，唯一字符-1
                    list1.get(t)[chars[i] - 'A']++;
                    sum--;
                }
            }
            int[] n = new int[26];
            n[chars[index] - 'A'] = 1;//初始化当前子串
            // 新添加该子串
            list1.add(n);
            sum++;
            if(i==chars.length-1)
                return ;
            function(chars, i+1,index);//以当前字符为之后的子串开头开始继续
        }
    }


    /**
     * 高解
     * 5ms
     * @param s
     * @return
     */
    public int uniqueLetterString2(String s) {
        /**
         * 可以将每个字符在哪个区间中是唯一标记出来，按照无重复情况时的算法算出其个数
         * 对于一个没有重复的字符串，易验证
         * 情况1：字符是“头元素”，那么出现次数可以通过：数组长度 - 元素下标位置 来计算出来。
         * 情况2：字符是“尾元素”，那么出现次数可以通过：元素下标位置 - (-1) 来计算出来。
         * 情况3：字符是“中间元素”，那么出现次数可以通过：(元素下标位置 - (-1)) * (数组长度 - 元素下标位置) 来计算出来。
         */
        int ans = 0;
        int[] tmp0 = new int[26]; //存储某一个字符前一个字符所在位置
        int[] tmp1 = new int[26]; //存储某个字符当前所处位置

        //默认值用-1填充
        Arrays.fill(tmp0, -1);
        Arrays.fill(tmp1, -1);

        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char now = chars[i];
            int index = now - 'A';
            if (tmp1[index] > -1) {  //如果之前存在该元素
                ans += (i - tmp1[index]) * (tmp1[index] - tmp0[index]); //计算上一个唯一含有该元素的子串
            }
            tmp0[index] = tmp1[index]; //把当前位置更新为这个字符前一个位置
            tmp1[index] = i;    //存储该字符当前所处位置
        }
        for (int i = 0; i < 26; i++) {
            if (tmp1[i] > -1) { //处理剩下未被处理的子串
                ans += (tmp1[i] - tmp0[i]) * (s.length() - tmp1[i]);
            }
        }
        return ans;
    }
}
